from typing import List
import random

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if k == 0 or not arr:
            return []

        def partition(a, s, t):
            pivot = a[s]
            i, j = s, t
            while i < j:
                while i < j and a[j] >= pivot:
                    j -= 1
                a[i] = a[j]
                while i < j and a[i] <= pivot:
                    i += 1
                a[j] = a[i]
            a[i] = pivot
            return i

        def quick_sort(a, s, t):
            if s < t:
                i = partition(a, s, t)
                quick_sort(a, s, i - 1)
                quick_sort(a, i + 1, t)

        quick_sort(arr, 0, len(arr) - 1)
        return arr[:k]

arr = [1, 3, 5, 7, 2, 4, 6, 8]
k = 4
print(Solution().smallestK(arr, k))